#include"SList.h"
//链表打印函数
void SLTPrint(SLTNode* phead)
{
        SLTNode* pcur = phead;
        while (pcur) {
            printf("%d->",pcur->x);
            pcur = pcur->next;
        }
        printf("NULL\n");//所有的 NULL都由 Print函数另外打印
}
//申请新节点(为尾插做基础)
SLTNode* SLTBuyNode(SLTDatatype x)
{
    //申请一份（自定义）结构体类型的动态空间，此一份动态空间可以存放结构体里的所有成员
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    //判断空间是否申请成功
    if(node == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    //给结点成员赋值
    node->x = x;
    node->next = NULL;
    //最后返回结点
    return node;
}
//尾插
void SLTPushBack(SLTNode** pphead,SLTDatatype x)
{
    //限制尾插不能插入 NULL
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if(*pphead == NULL)//判断链表是否为空，为空的话直接将phead 指向 newnode
    {
        *pphead = newnode;
    }
    else//不为空，遍历链表，找到尾结点，并尾插
    {
        SLTNode* pcur = *pphead;//创建临时一级指针遍历链表，找到尾结点
        //pcur的next为空时，即走到了链表最后一位
        while (pcur->next) {
            pcur = pcur->next;
        }
        //尾插
        pcur->next = newnode;
    }
}
//头插
void SLTPushFront(SLTNode** pphead,SLTDatatype x)
{
    //限制头插不能插入 NULL
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);//依旧是先申请新节点
    if (*pphead == NULL) {
        *pphead = newnode;
    }
    else
    {
        //SLTNode* tmp = *pphead;//先把头结点指针的值（即头结点地址）复制保存一下
        //*pphead = newnode;//把头接点指针指向 newnode
        //newnode->next = tmp;//再把 newnode 的 next 指向原头结点
        
        newnode->next = *pphead;//先把newnode 中 next 指向头结点地址
        *pphead = newnode;//在直接把头结点 plist指向 newnode
    }
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
    //链表的头结点指针和二级指针都不能为空
    assert(pphead && *pphead);
    //判断链表是否仅含一个结点，此时 prev 为空，无法被解引用，因此要直接把头结点释放并置空。
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    }
    else{
        //定义尾结点和前结点
        SLTNode* ptail = *pphead;
        SLTNode* prev = NULL;
        //遍历链表找到尾结点
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        //将原尾结点释放并置空
        free(ptail);
        ptail = NULL;
        //前节点 next 指向NULL
        prev->next = NULL;
    }
}
//头删
void SLTPopFront(SLTNode** pphead)//不用单独处理链表只有一个结点的情况，因为头删中 pcur可以为空
{
    assert(pphead && *pphead);
        //创建一个 pcur直接指向第二个结点（头结点的 next）
        SLTNode* pcur = (*pphead)->next;
        //把头结点释放掉
        free(*pphead);
        //最后直接头结点地址指针指向 pcur
        *pphead = pcur;
}
//查找
SLTNode* SLTFind(SLTNode* phead,SLTDatatype x)
{
    assert(phead);//链表不能为空
    //定义一指针遍历链表
    SLTNode* pcur = phead;
    while (pcur)
    {
        if (pcur->x == x)//当 pcur结点的值等于我们要查找的值时，直接返回该结点地址
        {
            return pcur;//找到后，返回其结点地址
        }
        pcur = pcur->next;
    }
    return NULL;//没找到则返回空指针
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDatatype x)
{
    //链表和 pos 都不能为空，且pos的范围要在链表结点数以内（但是要统计结点数就只能遍历整个链表，效率较为低下）
    assert(pphead);
    assert(pos);
    //定义一个 prev 指针找到 pos 之前的位置
    SLTNode* prev = *pphead;
    //特殊情况:对链表的头结点之前插入
    if (prev == pos) {
        SLTPushFront(pphead, x);
    }
    else{
        //申请新结点
        SLTNode* newnode = SLTBuyNode(x);
        //遍历链表，找到pos 之前的结点
        while (prev->next != pos) {
            prev = prev->next;
        }
        //前后接上结点即可
        prev->next = newnode;
        newnode->next = pos;
    }
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos,SLTDatatype x)
{
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);//申请新结点
        SLTNode* next = pos->next;
        pos->next = newnode;
        newnode->next = next;
}
//删除指定位置的数据
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
    //pphead也要和（*pphead）头结点指针 一起判断是否为空，因为无法确定前置操作是否将其置空
    assert(pphead && *pphead);
    assert(pos);
    //pos为头结点的时候，直接执行头插操作
    if (pos == *pphead) {
        SLTPopFront(pphead);
    }
    //删除 pos 位置
    else{
        //定义 prev 遍历链表找到pos 前的位置，
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        //最后将pos 置空
        free(pos);
        pos = NULL;
    }
}
//删除指定位置之后的数据
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);//确保 pos 的后一位不为空，才能被删除
    //先新定义变量把 pos->next 保存下来，以供后续释放并置空
    SLTNode* del = pos->next;
    pos->next = (pos->next)->next;//改变结点指向
    //将 pos 结点释放并置空
    free(del);
    del = NULL;
}
//销毁整个链表
void SLTDestroy(SLTNode** pphead)
{
    //限制链表和其二级指针不能为空
    assert(pphead && *pphead);
    SLTNode* pcur = *pphead;//定义一个指向头结点的指针，遍历链表，挨个销毁结点
    while (pcur) {
        SLTNode* next = pcur->next;//伴随 pcur 其后，遍历链表以供找到下一个链表的地址
        free(pcur);
        //pcur = NULL;//此时不需要置空，因为头结点将在循环外置空，而头结点置空后，链表里的其他结点即使没置空也无法被访问了，
        //所以仅释放空间却没有置空也不会构成非法访问，当然也可以每个都置空，没有严格的规定。
        pcur = next;//释放后，把 pcur 指向 next 指针
    }
    *pphead = NULL;
}
